home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1994 / MacHack 1994.toast / MacHack™94 / Talks & Papers / Timothy Knox / Help / Help Files / Miscellaneous / Memoizing < prev    next >
Text File  |  1994-06-24  |  1KB  |  48 lines
  1. {••• Let's have fun with memo-functions •••}
  2.  
  3. {••• A function that looks for a memoized value    •••}
  4. {••• o = look for it, t = in it, s = access result •••}
  5. {•••        f = thunk to evaluate upon failure     •••}
  6.  
  7. (define (lookup o t s f)
  8.   (letrec [((lookup t)
  9.              (cond (null? t) (f)
  10.                    (let [(pr (0 t))]
  11.                         (cond (equal? (0 pr) o) (s pr)
  12.                               (lookup (-1 t))))))]
  13.           (lookup t)))
  14.  
  15. {••• The memoizer itself, p is the function to memoize •••}
  16. {•••          s is CDR access (-1) and f memoizes      •••}
  17.  
  18. (define (memo p)
  19.   (let [(t ())]
  20.        (lambda a
  21.           (lookup a
  22.                   t
  23.                   -1
  24.                   (lambda()
  25.                     (let [(v (apply p a))]
  26.                          (=! t (force (cons (cons a v) t)))
  27.                          v))))))
  28.  
  29. {••• A small macro to extend the Help language •••}
  30.  
  31. (defmacro (defmemo f | b)
  32.   (cond (cons? f) `(define ,(0 f) (memo (lambda ,(-1 f) ,@b)))
  33.         `(define ,f (memo ,@b))))
  34.  
  35. {••• An example with a memoized NAIVE fibonnacci •••}
  36.  
  37. (defmemo (f n)
  38.   (cond (<? n 2) 1
  39.         (+ (f (1- n))(f (- n 2)))))
  40.  
  41. {••• Timing on a SE-30 •••}
  42. (chrono (f 100))
  43. { = [573147844013817084101  7.500000000000000000e-1  0.000000000000000000e+0] }
  44.  
  45. {••• Now it's memoized… let's try again •••}
  46. (chrono (f 100))
  47. { = [573147844013817084101  0.000000000000000000e+0  0.000000000000000000e+0] }
  48.